package cuiyt.algorithm.dfs;

import algorithm.TreeNode;
import org.apache.hadoop.yarn.webapp.hamlet.Hamlet;
import org.apache.log4j.spi.RootLogger;

import java.util.LinkedList;
import java.util.List;

/**
 * @author cyt
 * @create 2020-08-24 17:43
 */
public class T897 {
    /**
     * 给你一个树，请你 按中序遍历 重新排列树，使树中最左边的结点现在是树的根，并且每个结点没有左子结点，只有一个右子结点。
     *
     * @param args
     */
    public static void main(String[] args) {

    }
    /**
     * 我们在树上进行中序遍历，就可以从小到大得到树上的节点。我们把这些节点的对应的值存放在数组中，它们已经有序。接着我们直接根据数组构件题目要求的树即可。
     *
     * @param root
     * @return
     */
    List<Integer> list = new LinkedList<Integer>();
    public TreeNode increasingBST(TreeNode root) {
        dfs(root);
        TreeNode ans = new TreeNode(0), cur = ans;
        for (int v: list) {
            cur.right = new TreeNode(v);
            cur = cur.right;
        }
        return ans.right;
    }

    public void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        list.add(root.val);
        dfs((root.right));
    }
}
